package Solutions;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Classname PalindromePartitioning
 * @Description TODO
 * @Date 2021/6/22 19:59
 * @Created by LengDanran
 * https://leetcode-cn.com/problems/palindrome-partitioning/
 */
public class PalindromePartitioning {

    /***
     * 执行结果：
     * 通过
     * 显示详情
     *
     * 添加备注
     * 执行用时：22 ms, 在所有 Java 提交中击败了7.52% 的用户
     * 内存消耗：51.4 MB, 在所有 Java 提交中击败了86.71% 的用户
     */
    List<List<String>> ans = new ArrayList<>();
    public List<List<String>> partition(String str) {

        if (str == null || str.length() == 0) return ans;
        helper(str, new ArrayList<>());
        return ans;
    }

    private void helper(String str, List<String> path) {
        if ("".equals(str)) ans.add(path);
        else {
            for (int i = 1; i <= str.length(); i++) {
                String tmp = str.substring(0, i);
                if (isPalindrome(tmp)) {// 是回文
                    path.add(tmp);// 添加到当前路径
                    helper(str.substring(i), new ArrayList<>(path));// 递归分割右边部分
                    path.remove(path.size() - 1);// 回溯移除添加的元素
                }
            }
        }
    }

    /***
     * 执行用时：16 ms, 在所有 Java 提交中击败了15.81% 的用户
     * 内存消耗：53 MB, 在所有 Java 提交中击败了18.33% 的用户
     */
    private boolean isPalindrome(String str) {
        if ("".equals(str)) return true;
        int left = 0, right = str.length() - 1;
        char[] chars = str.toCharArray();
        while (left < right) {
            if (chars[left++] != chars[right--]) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new PalindromePartitioning().partition("abab"));
    }

}
